package tree;

import printer.BinaryTreeInfo;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉搜索树
 * 设计：
 *
 * @author Mxb
 * @version 1.0
 * @date 2020/3/4 13:22
 */
public class BinarySearchTree<E> implements BinaryTreeInfo {
    // 记录多少个节点
    private int size;
    // 根节点
    private Node root;
    // 比较器
    private Comparator<E> comparator;

    // 有参传比较器的 构造方法
    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    //无参构造
    public BinarySearchTree() {
        this(null);
    }

    /**
     * 返回二叉树的 容量
     *
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * 判断二叉搜索树 是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 清空树
     */
    public void clear() {

    }

    /**
     * 添加树 节点
     *
     * @param element
     */
    public void add(E element) {
        // element不能为空
        checkNotNullElement(element);
        //添加的为根节点
        if (root == null) {
            //添加为第一个节点  根节点
            root = new Node(element, null);
            size++;
            return;
        }
        // 添加的不是第一个节点，从根节点开始的比较查询
        Node<E> node = root;
        //找到要添加元素的父节点
        Node<E> parent = root;
        int cmp = 0;

        // 找到最后退出
        while (node != null) {
            //比较方法
            cmp = compare(element, node.element);

            // 向左向右之前 保存父节点
            parent = node;

            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {
                // 相等 直接返回

                return;
            }
        }
        //新节点
        Node<E> newNode = new Node(element, parent);
        // 插入到父节点 那个位置
        if (cmp > 0) {
            //插到父节点 右边
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        // 容量+1
        size++;
    }

    /**
     * 移除指定节点
     *
     * @param element
     * @return
     */
    public int remove(E element) {
        return 1;
    }

    /**
     * 返回值大于0 e1>e2 反之同理
     *
     * @param element
     * @return
     */
    public boolean contains(E element) {

        return false;
    }

    /**
     * 比较方法 逻辑
     *
     * @param e1
     * @param e2
     * @return 大于0 e1>e2，小于0 e1<e2
     */
    private int compare(E e1, E e2) {
        //调用 这
        //return e1.compareTo(e2);
        //return comparator.compare();
        // 优先用比较器
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }
        //comparator为空 强转
        return ((Comparable<E>) e1).compareTo(e2);
    }

    /**
     * 检测元素不为空
     *
     * @param element
     */
    private void checkNotNullElement(E element) {
        if (element == null) {
            // 抛出 非法参数异常
            throw new IllegalArgumentException("元素不能为空！");
        }
    }

    /**
     * 内部类定义节点类
     *
     * @param <E>
     */
    private static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;  //不一定有
        Node<E> parent; //父节点

        // 构造方法，创建对象时使用
        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        /**
         * 判断结点 是否是叶子结点 方法
         *
         * @return
         */
        public boolean isleaf() {
            return left == null && right == null;
        }

        /**
         * 判断是否有二个子结点
         *
         * @return
         */
        public boolean hastTwoChildren() {
            return left != null && right != null;
        }
    }

    /**
     * 前序遍历
     */
    public void preorderTraversal() {
        preorderTraversal(root);
    }

    /**
     * 前序遍历
     * 采用 递归调用
     * ：先根 左 右
     *
     * @param node
     */
    private void preorderTraversal(Node<E> node) {
        // 设置递归结束条件
        if (node == null) return;

        //preorderTraversal(node);
        System.out.print(node.element + " ");
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }

    /**
     * 中序遍历
     */
    public void ineorderTraversal() {
        ineorderTraversal(root);
    }

    /**
     * 中序遍历
     * 采用 递归调用
     * ：先左 根 右
     *
     * @param node
     */
    private void ineorderTraversal(Node<E> node) {
        if (node == null) return;
        //preorderTraversal(node);
        ineorderTraversal(node.left);
        System.out.print(node.element + " ");
        ineorderTraversal(node.right);
    }

    /**
     * 后序遍历
     */
    public void postorderTraversal() {
        postorderTraversal(root);
    }

    /**
     * 采用 递归调用
     *
     * @param node
     */
    private void postorderTraversal(Node<E> node) {
        if (node == null) return;
        //preorderTraversal(node);
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.print(node.element + " ");
    }

    //层序遍历
    public void levelOrder() {
        if (root == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        //根节点入队  队列
        //queue.offer(root);
        //while (!queue.isEmpty()) {
        //    // 根出队  访问
        //    Node<E> node = queue.poll();
        //    System.out.print(node.element + " ");
        //    // 根的左子节点入队
        //    if (node.left != null) {
        //        queue.offer(node.left);
        //    }
        //    if (node.right != null) {
        //        queue.offer(node.right);
        //    }
        //}
        queue.offer(root);

        while (!queue.isEmpty()) {
            // 将根 节点出队 进行访问
            Node<E> poll = queue.poll();

            System.out.print(poll.element + " ");

            if (poll.left != null) {
                // 左不等于 空 入队
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
        }
    }

    /**
     * 定义一个接口
     * ：访问器
     *
     * @param <E>
     */
    public static abstract class Visitor<E> {
        // 记录停止 状态
        boolean stop;

        /**
         * 如果返回 true，表示停止遍历（默认false）
         *
         * @param element
         * @return
         */
        abstract boolean visit(E element);
    }

    public void levelOrder(Visitor<E> visitor) {
        if (root == null || visitor == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        //根节点入队
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 根出队
            Node<E> node = queue.poll();
            //打印
            //System.out.print(node.element + " ");
            //传出节点 元素内容传出去
            boolean visit = visitor.visit(node.element);
            // 如果visit 等于true 直接返回
            if (visit) {
                return;
            }

            // 根的左子节点入队
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    /**
     * 前序遍历
     * ：接口实现
     *
     * @param visitor
     */
    public void preorder(Visitor<E> visitor) {
        //if(root == null || visitor == null) return;
        preorder(root, visitor);
    }

    private void preorder(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;

        //if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);

        preorder(node.left, visitor);
        preorder(node.right, visitor);
    }

    /**
     * 中序遍历
     * ：接口实现
     *
     * @param visitor
     */
    public void inorder(Visitor<E> visitor) {
        //if (visitor == null) return;
        inorder(root, visitor);
    }

    private void inorder(Node<E> node, Visitor<E> visitor) {
        // visitor 停止递归
        if (node == null || visitor.stop) return;

        inorder(node.left, visitor);

        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);

        inorder(node.right, visitor);
    }

    /**
     * 后序遍历
     * ：接口实现
     *
     * @param visitor
     */
    public void postorder(Visitor<E> visitor) {
        if (visitor == null) return;
        postorder(root, visitor);
    }

    private void postorder(Node<E> node, Visitor<E> visitor) {
        // visitor 停止递归
        if (node == null || visitor.stop) return;

        postorder(node.left, visitor);
        postorder(node.right, visitor);  //visitor.stop == true

        //停止递归  将值存起来，再遍历时发现为true就不递归了
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);

    }

    public boolean isComplate() {
        return isComplate(root);
    }

    /**
     * 判断1课树是否是 完全二叉树
     *
     * @param root
     * @return
     */
    private boolean isComplate(Node<E> root) {
        if (root == null) return false;
        //使用层序遍历
        Queue<Node<E>> queue = new LinkedList<>();
        // 根节点入队
        queue.offer(root);
        // 标记 叶子结点
        boolean leaf = false;
        while (!queue.isEmpty()) {
            // 出队
            Node<E> node = queue.poll();
            // 叶子结点判断
            if (leaf && !node.isleaf()) return false;

            // 第一种情况  左右都 不为空
            //if (node.hastTwoChildren()) {
            if (node.left != null && node.right != null) {
                // 左右 都入队
                queue.offer(node.left);
                queue.offer(node.right);
                // 第二种情况 不是完全二叉树
            } else if (node.left == null && node.right != null) {
                return false;
                // 第三种情况  省略
                //(node.left != null && node.right == null || node.left == null && node.right == null
            } else {
                // 后边的都必须是叶子结点
                leaf = true;
                // 只要左边不为空 就入队
                if (node.left != null) {
                    queue.offer(node.left);
                }
            }

        }
        // 都符合 是完全二叉树
        return true;
    }

    /**
     * 打印方法 需要实现的 4个方法
     *
     * @return
     */
    @Override
    public Object root() {
        // 根节点
        return root;
    }

    @Override
    public Object left(Object node) {
        // 左子树 是谁
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        // 右子树 是谁
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        //打印节点元素的值

        // 打印 节点+父节点的值
        Node<E> myNode = (Node<E>) node;
        String parentString = "null";
        if (myNode.parent != null) {
            parentString = myNode.parent.element.toString();
        }
        return myNode.element + "_" + parentString;
    }

    /**
     * 利用前序遍历梳妆打印 二叉树
     *
     * @return
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        toString(root, sb, "");
        return sb.toString();
    }

    /**
     * 使用前序遍历 树状打印二叉树
     *
     * @param node
     * @param sb
     * @param prefix
     */
    public void toString(Node<E> node, StringBuilder sb, String prefix) {
        if (node == null) return;
        toString(node.left, sb, prefix + "L--");
        sb.append(prefix).append(node.element).append("\n");
        toString(node.right, sb, prefix + "R--");
    }

    /**
     * 计算返回二叉树的高度
     *
     * @return
     */
    public int height() {
        height(root);
        return 0;
    }

    /**
     * 递归方式实现：
     * 返回当前节点的高度
     *
     * @param node
     * @return
     */
    public int height(Node<E> node) {
        if (node == null) return 0;
        int max = Math.max(height(node.left), height(node.right));
        return max + 1;
    }

    /**
     * 非递归方式，使用层序遍历
     *
     * @return
     */
    public int height2() {
        // 树的高度
        int height = 0;
        // 存储每一层的元素数量
        int rowSize = 1;
        Queue<Node> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            rowSize--;


            // 根的左子节点入队
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            // 即将访问下一层
            if (rowSize == 0) {
                rowSize = queue.size();
                height++;
            }
        }
        return height;
    }
}
